package leetcode_core.leetcode_3;

import java.util.Comparator;
import java.util.PriorityQueue;

public class MergeKLists {
    public class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length ==0){
            return null;
        }
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        for (ListNode list : lists) {
            if(list!=null){
                pq.add(list);
            }
        }
        while (!pq.isEmpty()){
            ListNode poll = pq.poll();
            p.next = poll;
            if(poll.next!=null){
                pq.add(poll.next);
            }
            p = p.next;
        }
        return dummy.next;
    }

}
